Technical Field
The present invention relates generally to the identification of components in a computer network and more particularly, to a system for generating universally unique identifiers (UUIDs) for software objects and other components in a network in which a large number of components may exist simultaneously and/or over a period of time.
Structured computer information depends heavily upon unique identification of data objects. Generation of unique identifiers for these data objects, as well as other computer network components, is a challenging problem. Because of the wide deployment and redeployment of computer systems and data, it is necessary for these identifiers to be unique over time and space. Such an identifier is generally termed a Universally Unique Identifier, or xe2x80x98UUIDxe2x80x99. In addition to the uniqueness requirement, which can be achieved by assigning identifiers through a central authority, it is also desirable to be able to generate new UUIDs rapidly via software, while still preserving the uniqueness of each object.
Solutions to this problem exist that create UUIDs based upon the IEEE 24-bit xe2x80x98company ID valuesxe2x80x99 that can be obtained from the IEEE Registration Authority. In addition, UUIDs may be created by using the various NAA (Network Address Authority) formats described in the Fibre Channel Physical and Signaling Interfacexe2x80x943 (FC-PH-3) Rev 9.4, Nov. 5, 1997.
There are usually three components to a UUID. The first component is the IEEE company ID assigned by the IEEE Registration Authority. This component is complex and slow to assign, as the registration process takes place via mail. The second component is the NAA format, consisting of additional bit combinations assigned to particular products under the control of the company owning the IEEE company ID. The third component is typically assigned by software managed by a particular product, such as a disk storage array controller. This third component consists of the bit combinations remaining in the UUID which are assigned (usually sequentially) to produce the complete UUIDs as needed.
There are two subclasses of these solutions. The first subclass is created with the assumption that there is a statistical improbability of generating duplicate UUIDs using timestamps and certain hashing techniques. The second subclass of solution utilizes persistent storage of previously generated UUIDs to prevent re-generation of duplicate UUIDs. The first solution is generally deemed to be unacceptable due to the unbounded behavior of duplicate UUIDs, which are inevitably created using that technique. Implementation of the second solution is challenging due to the expense of high speed persistent storage (e.g., reliable battery backed up RAM) and the low speed of inexpensive persistent storage (e.g., flash memory).
The present invention overcomes the aforementioned problems of the prior art and achieves an advance in the field by providing a method which combines the high speed of volatile RAM (without a requirement for battery backup) and the low cost of non-volatile memory such as flash memory (without the requirement for high speed) to generate identifiers that are consistently unique.
In accordance with the method of the present invention, the third component of the UUID (discussed above) generated by a particular product is further divided into two sub-fields. One (sub-) field is stored in (relatively slow) non-volatile memory, and incremented infrequently. The other (sub-) field is stored in relatively fast, volatile RAM, that can be incremented quickly. During normal operation, the product creating the UUIDs generates new UUIDs by incrementing the field stored in RAM. When overflow of the RAM field occurs, the field stored in non-volatile memory is incremented. The size of the field stored in RAM is selected to cause the more expensive incrementing of non-volatile memory to occur sufficiently infrequently to minimize the impact of slow access, while maintaining a reasonable lifetime. If the product generating the UUIDs should lose the contents of RAM (due to reboot, power failure, or malfunction) it merely increments the field in non-volatile memory and resets the RAM field to zero.
When using flash memory, which has a limited number of erase/write cycles, the present invention takes advantage of the fact that multiple writes can be performed between erase cycles, as long as they only change bits from ones (1) to zeros (0), and not vice-versa. The present invention operates by initializing a block of flash memory to all ones, and then sequentially clearing (zeroing) the bits to generate each subsequent unique identifier. This method provides the equivalent of a counter that can count up to the number of available bits in the non-volatile memory block while reducing the number of flash memory erase cycles to one cycle for each time all the bits are cleared. Reducing the number of flash erase cycles is of critical importance, since flash memory is limited in the number of erase operations that can be performed over the lifetime of the memory.